﻿HmJS.$Import('core.core');

HmJS.register('lang.array', function ($) {

	// #region -- Private Methods for Array.sortBy --

	var keyPaths = [];

	var saveKeyPath = function (path) {
		keyPaths.push({
			sign: (path[0] === '+' || path[0] === '-') ? parseInt(path.shift() + 1) : 1,
			path: path
		});
	};

	var valueOf = function (object, path) {
		var ptr = object;
		path.each(function (key) { ptr = ptr[key]; });
		return ptr;
	};

	var comparer = function (a, b) {
		for (var i = 0, l = keyPaths.length; i < l; i++) {
			aVal = valueOf(a, keyPaths[i].path);
			bVal = valueOf(b, keyPaths[i].path);
			if (aVal > bVal) return keyPaths[i].sign;
			if (aVal < bVal) return -keyPaths[i].sign;
		}
		return 0;
	};

	// #endregion

	// #region -- Private Methods for Array.sortOn --

	Array.CASEINSENSITIVE = 1;
	Array.DESCENDING = 2;
	Array.UNIQUESORT = 4;
	Array.RETURNINDEXEDARRAY = 8;
	Array.NUMERIC = 16;

	var dup_fn = function (field, field_options) {
		var filtered = (field_options & Array.NUMERIC)
                   ? this.map(function (item) { return item[field].toFloat(); })
                   : (field_options & Array.CASEINSENSITIVE)
                   ? this.map(function (item) { return item[field].toLowerCase(); })
                   : this.map(function (item) { return item[field]; });
		return filtered.length !== [].combine(filtered).length;
	};

	var sort_fn = function (item_a, item_b, fields, options) {
		return (function sort_by(fields, options) {
			var ret, a, b,
          opts = options[0],
          sub_fields = fields[0].match(/[^.]+/g);

			(function get_values(s_fields, s_a, s_b) {
				var field = s_fields[0];
				if (s_fields.length > 1) {
					get_values(s_fields.slice(1), s_a[field], s_b[field]);
				} else {
					a = s_a[field].toString();
					b = s_b[field].toString();
				}
			})(sub_fields, item_a, item_b);

			if (opts & Array.NUMERIC) {
				ret = (a.toFloat() - b.toFloat());
			} else {
				if (opts & Array.CASEINSENSITIVE) { a = a.toLowerCase(); b = b.toLowerCase(); }

				ret = (a > b) ? 1 : (a < b) ? -1 : 0;
			}

			if ((ret === 0) && (fields.length > 1)) {
				ret = sort_by(fields.slice(1), options.slice(1));
			} else if (opts & Array.DESCENDING) {
				ret *= -1;
			}

			return ret;
		})(fields, options);
	};

	// #endregion Array.sortOn

	// #region -- Private Methods for Array.quickSort --

	var doSort = function (a, s, e) {
		if (s < e) {
			var pos = partition(a, s, e);
			doSort(a, s, pos - 1);
			doSort(a, pos + 1, e);
		}
	};

	var partition = function (a, st, en) {
		var s = st;
		var e = en + 1;
		var temp = a[s];
		while (1) {
			while (a[++s] < temp) { ; }
			while (a[--e] > temp) { ; }
			if (s > e) { break; }
			var tem = a[s];
			a[s] = a[e];
			a[e] = tem;
		}
		if (st != e) {
			a[st] = a[e];
			a[e] = temp;
		}
		return e;
	};

	var internalQuickSort = function (a, lowIndex, highIndex, fn) {
		if (lowIndex < highIndex) {
			var pos = internalPartition(a, lowIndex, highIndex, fn);
			internalQuickSort(a, lowIndex, pos - 1, fn);
			internalQuickSort(a, pos + 1, highIndex, fn);
		}
	};

	var internalPartition = function (a, lowIndex, highIndex, fn) {
		var lowI = lowIndex;
		var highI = highIndex;
		var pivot = a[lowI];
		while (true) {
			do { lowI++; } while (fn.call(null, a[lowI], pivot, this) < 0);
			while (fn.call(null, a[highI], pivot, this) > 0) { highI--; }
			if (lowI >= highI) { break; }
			var tmp = a[lowI];
			a[lowI] = a[highI];
			a[highI] = tmp;
		}
		if (lowIndex != highI) {
			a[lowIndex] = a[highI];
			a[highI] = pivot;
		}
		return highI;
	};

	// #endregion quickSort

	// #region -- Array.stableSort --

	var defaultSortFunction = function (a, b) {
		return a > b ? 1 : (a < b ? -1 : 0);
	};

	// #endregion

	// #region -- Array.each.async,Object.each.async --

	/*
	---
	version: 1.0-0
	description: An async iteration mechanism for array and object
	license: MIT-style
	download: http://mootools.net/forge/p/each_async
	source: http://github.com/arieh/Each.async

	authors:
	- Arieh Glazer

	requires:
	- core/1.3: [Core]

	provides: [Array.each.async,Object.each.async]

	注意: 看测试，好像只对element对象操作时快过Array.each
	...
	*/

	var async = function (iter, func, bind, time) {
		var k;
		function delayed(item, key, obj) {
			func.call(bind, item, key, obj);
		}

		for (k in iter) {
			if (iter.hasOwnProperty(k)) {
				if (bind) {
					delayed.delay(time || 0, null, [iter[k], k, iter]);
				} else {
					setTimeout(func, time || 0, iter[k], k, iter);
				}
			}
		}
	};

	Array.each.async = Object.each.async = async;

	// #endregion

	Array.extend({

		dim4hm: function (dimension, initial) {
			// 经测试，比先用new Array(dimension),再赋值要快
			var ary = [];
			for (var i = 0; i < dimension; i++) {
				ary[i] = initial;
			}
			return ary;
		}

	});

	Array.implement({

		// #region -- Array.sortBy --

		/*
		---
		script: array-sortby.js
		version: 1.3.0-0
		description: Array.sortBy is a prototype function to sort arrays of objects by a given key.
		license: MIT-style
		download: http://mootools.net/forge/p/array_sortby
		source: http://github.com/eneko/Array.sortBy

		authors:
		- Eneko Alonso: (http://github.com/eneko)
		- Fabio M. Costa: (http://github.com/fabiomcosta)

		credits:
		- Olmo Maldonado (key path as string idea)

		provides:
		- Array.sortBy

		requires:
		- core/1.3.0:Array

		...
		*/

		sortBy: function () {
			keyPaths.empty();
			Array.each(arguments, function (argument) {
				switch (typeOf(argument)) {
					case "array": saveKeyPath(argument); break;
					case "string": saveKeyPath(argument.match(/[+-]|[^.]+/g)); break;
				}
			});
			return this.sort(comparer);
		},

		// #endregion

		// #region -- Array.sortOn --

		/*
		---

		script: Array.sortOn.js
		version: 1.0-1
		description: Adds Array.sortOn function and related constants that works like in ActionScript for sorting arrays of objects (applying all same strict rules)
		license: MIT-style license.
		download: http://mootools.net/forge/p/array_sorton_js
		source: http://github.com/gonchuki/mootools-Array.sortOn

		authors:
		- gonchuki

		docs: http://www.adobe.com/livedocs/flash/9.0/ActionScriptLangRefV3/Array.html#sortOn()

		requires:
		- core/1.3+: [Array]

		provides: 
		- [Array.sortOn, Array.CASEINSENSITIVE, Array.DESCENDING, Array.UNIQUESORT, Array.RETURNINDEXEDARRAY, Array.NUMERIC]

		...
		*/

		sortOn: function (fields, options) {
			fields = Array.from(fields);
			options = Array.from(options);

			if (options.length !== fields.length) { options = []; }

			if ((options[0] & Array.UNIQUESORT) && (fields.some(function (field, i) { return dup_fn(field, options[i]); }))) { return 0; }

			var curry_sort = function (item_a, item_b) {
				return sort_fn(item_a, item_b, fields, options);
			};

			if (options[0] & Array.RETURNINDEXEDARRAY) {
				return this.slice().sort(curry_sort);
			} else {
				this.sort(curry_sort);
			}
		},

		// #endregion Array.sortOn

		// #region -- Array.quickSort --

		// 数值数组快速排序，替代原生Array.prototype.sort()函数
		// 
		// Syntax: myArray.quickSort();
		// 
		// Arguments: fn(item1, item2, array)
		// 
		// Returns: 
		// 
		// Examples: 
		// 
		quickSort: function (fn) {
			var length = this.length;
			if (length < 2) { return this; }
			if (arguments.length > 0) {
				internalQuickSort(this, 0, length - 1, fn);
			} else {
				doSort(this, 0, this.length - 1);
			}
			return this;
		},

		// #endregion Array.quickSort

		// #region -- Array.More --

		/*
		---
		version: 0.1.7-0
		description: Additional methods for the Array class
		license: MIT-style
		download: http://mootools.net/forge/p/array_more
		source: http://github.com/dArignac/mootools_array_more

		authors:
		- Alexander Herrmann

		requires:
		core/1.3.2: [Array]

		provides:
		- Array.intersect
		- Array.differentiate
		- Array.getRange
		- Array.reverse4hm()
		...
		*/

		/**
		* Creates an intersection of the current array and the given one.
		* Returns as new array.
		* @param Array other	the array to use
		* @return Array
		*/
		intersect: function (other) {
			var cpy = this.slice();
			this.each(function (el) {
				if (other.indexOf(el) < 0) {
					cpy.splice(cpy.indexOf(el), 1);
				}
			}, this);
			return cpy;
		},

		/**
		* Returns the symmetric difference between this array and the given one.
		* Means the items both arrays include are removed from both and then both are combined.
		* @param Array other	the array to use
		* @return Array
		*/
		differentiate: function (other) {
			var src = this.slice();
			var cmp = other.slice();
			other.each(function (elem) {
				if (src.indexOf(elem) > -1) {
					// remove from both
					src.splice(src.indexOf(elem), 1);
					cmp.splice(cmp.indexOf(elem), 1);
				}
			}, this);
			// combine remaining items
			return src.combine(cmp);
		},

		/**
		* Returns the given number of elements from the array starting 
		* at the given index.
		* @param int start index
		* @param int number of elements to return - if not given all elements from start index will be returned
		* @return Array
		*/
		getRange: function (start, elements) {
			var res = [];
			var j = 0;
			// check if no element count is given
			var upper = this.length;
			if (undefined != elements) {
				var upper = start + elements > this.length ? this.length : start + elements;
			}
			if (start >= 0) {
				for (var i = start; i < upper; i++) {
					res[j++] = this[i];
				}
			}
			return res;
		},

		/**
		* Returns the array as array in reverse order.
		* @return Array
		*/
		reverse4hm: function () {
			var reversed = [];
			for (var i = this.length - 1; i >= 0; i--) {
				reversed.push(this[i]);
			}
			return reversed;
		},

		// #endregion Array.More

		// #region -- Array.Math --

		/*
		---
		name: Array.Math

		description: Array.Math is an extension for Array with Math methods

		license: MIT-style

		authors:
		- Arian Stolwijk

		requires:
		- Core/Array

		provides:
		- Array.Math
		- Array.sum
		- Array.product
		- Array.quotient
		- Array.power
		- Array.add
		- Array.substract
		- Array.count
		- Array.range
		- Array.sequence
		- Array.median
		- Array.variance
		- Array.stdDeviation
		- Array.transpose
		- Array.dot
		- Array.cross
		- Array.project
		- Array.determinant
		- Array.vectorLength
		- Array.normalize
		- Array.slope
		- Array.distance
		...
		*/

		toNumbers: function () {
			return this.map(Number.from);
		},

		/**
		# 苦苦的苦瓜
		# 2011-08-12
		# 用快速排序法代替
		sortNumbers: function () {
		return this.sort(function(a, b){
		return a - b;
		});
		},
		**/

		// #region - Calculus -

		/**
		# 这里的sum已经覆盖了core.array.js中的sum
		**/
		sum: function (start, length) {
			var sum = 0,
				start = start ? start : 0,
				length = length ? length : this.count() - start;
			length = start ? length + 2 : length;
			for (var i = start; i < length; i++) sum += this[i];
			return sum;
		},

		product: function (p) {
			var isArray = typeOf(p) == 'array';
			return this.map(function (entity, i) {
				return entity * (isArray ? p[i] : p);
			});
		},

		quotient: function (q) {
			var isArray = typeOf(q) == 'array';
			return this.map(function (entity, i) {
				return entity / (isArray ? q[i] : q);
			});
		},

		power: function (pow) {
			var isArray = typeOf(pow) == 'array';
			return this.map(function (entity, i) {
				return Math.pow(entity, isArray ? pow[i] : pow);
			});
		},

		add: function (add) {
			var isArray = typeOf(add) == 'array';
			return this.map(function (entity, i) {
				return entity + (isArray ? add[i] : add);
			});
		},

		subtract: function (subtract) {
			var isArray = typeOf(subtract) == 'array';
			return this.map(function (entity, i) {
				return entity - (isArray ? subtract[i] : subtract);
			});
		},

		count: function () {
			return this.length;
		},

		range: function (start, end, step) {
			if (!step) { step = 1; }
			for (var i = start; i <= end; i += step) {
				this.push(i);
			}
			return this;
		},

		sequence: function (fn, start, length) {
			if (start == null) { start = 0; }
			if (!length) { length = 10; }
			for (var i = start; i < (start + length); i++) {
				var e = fn.call(this, i);
				if (e != null || e != undefined) {
					this[i] = e;
				}
			}
			return this;
		},

		// #endregion

		// #region - Statistics -

		/**
		# 返回结果之后，本数组也已经冲排序了
		**/
		median: function () {
			var arr = this.toNumbers().sortNumbers();
			var middle = (arr.length + 1) / 2;
			return (arr.length % 2) ? arr[middle - 1] : (arr[middle - 1.5] + arr[middle - 0.5]) / 2;
		},

		variance: function () {
			var length = this.count(),
					avg = this.sum() / length;
			return this.subtract(avg).power(2).sum() / length;
		},

		stdDeviation: function () {
			return Math.sqrt(this.variance());
		},

		// #endregion

		// #region - Vector and matrices -

		transpose: function () {
			var trans = [];
			this.each(function (row, y) {
				row.each(function (col, x) {
					if (!trans[x]) { trans[x] = []; }
					trans[x][y] = col;
				});
			});
			return trans;
		},

		dot: function (arr2) {
			return this.product(arr2).sum();
		},

		cross: function (arr2) {
			return [
			this[1] * arr2[2] - this[2] * arr2[1],
			this[2] * arr2[0] - this[0] * arr2[2],
			this[0] * arr2[2] - this[2] * arr2[0]
		];
		},

		projection: function (proj) {
			return proj.product(this.dot(proj) / proj.dot(proj));
		},

		determinant: function () {
			if (this.count() != 2) return 0; // only 2x2 matrices for now
			return this[0][0] * this[1][1] - this[0][1] * this[1][0];
		},

		vectorLength: function () {
			return Math.sqrt(this.dot(this));
		},

		normalize: function () {
			return this.quotient(this.vectorLength());
		},

		angle: function (a) {
			return Math.acos(this.dot(a) / (this.vectorLength() * a.vectorLength()));
		},

		// #endregion

		// #region - Geometry -

		slope: function (p2) {
			return (p2[1] - this[1]) / (p2[0] - this[0]);
		},

		distance: function (p2) {
			return Math.sqrt(this.subtract(p2).power(2).sum());
		},

		// #endregion

		// #endregion

		// #region -- Array.stableSort --

		/*
		---
		script: Array.stableSort.js
		version: 1.1.2-1
		description: Add a stable sort algorithm for all browsers
		license: MIT-style license.
		download: http://mootools.net/forge/p/array_stablesort
		source: http://github.com/yoricksijsling/mooArrayStableSort

		authors:
		- Yorick Sijsling

		requires:
		core/1.3: '*'

		provides:
		- [Array.stableSort, Array.mergeSort]
		...
		*/

		/*
		Array.stableSort
		================

		Adds a stable sort function to older browsers. Since Google Chrome 12, all browsers have stable sorting by default.
		A stable sort behaves more intuitive when you're sorting a dataset multiple times on different keys (e.g. a sortable table) and the result is always predictable.

		How to use
		----------

		You'll need an array with test data:

		var myArray = [ [1,5], [3,3], [2,7], [1,4], [1,8]];

		Now sort on the first item:

		myArray.stableSort(function(a,b) {
		return a[0] > b[0] ? 1 : (a[0] < b[0] ? -1 : 0);
		});

		Result:

		[ [1,5], [1,4], [1,8], [2,7], [3,3] ];

		Note that an unstable sort algorithm might just as well have given any of these:

		[ [1,4], [1,8], [1,5], [2,7], [3,3] ];
		[ [1,8], [1,4], [1,5], [2,7], [3,3] ];
		[ [1,4], [1,5], [1,8], [2,7], [3,3] ];
		...

		Notes
		-----

		More information on stable sorting on <http://en.wikipedia.org/wiki/Sorting_algorithm#Stability>

		Only old versions of Chrome(< 12), Firefox(< 3) and Opera(< 10) use an unstable sort algorithm. All other browsers (at least Firefox 3+, Internet Explorer, Safari and Opera 10+) use a stable sort.

		It's implemented using a merge sort. In Chrome 5 it's about half as fast as the default sort (firefox and opera are slower). Time complexity is the same, O(n log n). The default sort will be used whenever possible.
		*/

		stableSort: function (compare) {
			// I would love some real feature recognition. Problem is that an unstable algorithm sometimes/often gives the same result as an unstable algorithm.
			return (Browser.chrome || Browser.firefox2 || Browser.opera9) ? this.mergeSort(compare) : this.sort(compare);
		},

		mergeSort: function (compare, token) {
			compare = compare || defaultSortFunction;
			if (this.length > 1) {
				// Split and sort both parts
				var right = this.splice(Math.floor(this.length / 2)).mergeSort(compare);
				var left = this.splice(0).mergeSort(compare); // 'this' is now empty.

				// Merge parts together
				while (left.length > 0 || right.length > 0) {
					this.push(right.length === 0 ? left.shift() :
											left.length === 0 ? right.shift() :
											compare(left[0], right[0]) > 0 ? right.shift() : left.shift());
				}
			}
			return this;
		}

		// #endregion

	}).alias({
		sortNumbers: 'quickSort'
	});

});
